package com.jxb.dp;

import java.util.HashSet;
import java.util.Set;

public class GameBag {

    public static void main(String[] args) {

    }

    //处理过程中需要一个二维数组进行定义
    private static class ArrayElement {
        //计算后的数组元素值
        private int value;
        //哪些物品的值组成了当前的数组元素
        private Set<Element> elements;

        public ArrayElement(int value, Element element) {
            this.value = value;
            this.elements = new HashSet<>();
            this.elements.add(element);
        }

        public ArrayElement(int value, Set<Element> elements) {
            this.value = value;
            this.elements = elements;
        }

        @Override
        public String toString() {
            return "BagElement{" +
                    "value=" + value +
                    ", elements=" + elements +
                    '}';
        }
    }

    //放入背包的物品
    private static class Element{
        private final String name;
        private final int value;//物品的价值
        private final int cost;//物品的花费

        public Element(String name,  int cost,int value) {
            this.name = name;
            this.value = value;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return "Element{" +
                    "name='" + name + '\'' +
                    ", value=" + value +
                    ", cost=" + cost +
                    '}';
        }
    }

    public void printArray(Element[] goods, int bagSize, ArrayElement[][] calc){
        for(int i=0;i<goods.length;i++){
            for(int j=0;j<bagSize;j++){
                //if( calc[i][j] !=null)
                System.out.print("i="+i+",j="+j+","+calc[i][j]+" ");
            }
            System.out.println("");
        }
    }

    public void printRow(int rowNo, int bagSize, ArrayElement[][] calc){
        System.out.println("当前行号："+ rowNo);
        for(int j=0;j<bagSize;j++){
            if( calc[rowNo][j] !=null)
                System.out.print("j="+j+","+calc[rowNo][j]+" ");
        }
        System.out.println("");
    }

    public void putBag(Element[] goods,int bagSize){
        int arrayX = goods.length + 1;
        int arrayY = bagSize + 1;
        ArrayElement[][] calcArray = new ArrayElement[goods.length][bagSize];
//        int[][] calcArray = new int[arrayX][arrayY];
        //遍历商品
        for (int i = 0;i<goods.length;i++) {
            //遍历包
            for (int j = 0;j<bagSize;j++) {
                //第一行数据做特殊处理
                if (i == 0) {
                    calcArray[i][j] = new ArrayElement(goods[i].value,goods[i]);
                }else {
                    //计算本单元格是否能放下当前物品
                    int spareSpace = j+1-goods[i].cost;
                    //放不下，直接使用上一行同列的数据
                    if(spareSpace < 0) {
                        calcArray[i][j] = calcArray[i-1][j];
                    }else {
                        //可以放下，判断上一行同列的值和当前商品的价值和剩余的空间哪个大
                        int preRow = i-1;
                        //上一行同列的值
                        int preRowValue = calcArray[preRow][j].value;
                        //当前商品的价值
                        int currentGoodsValue = goods[i].value;
                        //是否有剩余空间，如果有，获取剩余空间的最大值
                        if (spareSpace > 0) {
                            currentGoodsValue += calcArray[preRow][spareSpace-1].value;
                        }
                        if (preRowValue >= currentGoodsValue) {
                            //使用上一行同列的数据
                            calcArray[i][j] = calcArray[preRow][j];
                        }else {
                            //空间只够存放当前物品
                            if (spareSpace == 0) {
                                calcArray[i][j] = new ArrayElement(currentGoodsValue,goods[i]);
                            }else {
                                Set<Element> newElement =
                                        (HashSet<Element>)((HashSet<Element>)calcArray[preRow][spareSpace-1].elements).clone();
                                newElement.add(goods[i]);
                                calcArray[i][j] = new ArrayElement(currentGoodsValue,newElement);
                            }
                        }
                    }
                }
            }
            //printArray(goods,bagSize,calcArray);
            printRow(i,bagSize,calcArray);
            System.out.println("------------------------------------");
        }
        System.out.println("最终结果： "+calcArray[goods.length-1][bagSize-1]);
    }

}
